package 二叉树高频题目_下_不含树型dp;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 冷加宝
 * @version 1.0
 */
// 收集累加和等于aim的所有路径
// 测试链接 : https://leetcode.cn/problems/path-sum-ii/
public class Code03_PathSumII {

    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
    }

    public List<List<Integer>> pathSum(TreeNode root, int aim) {
        // 返回结果
        List<List<Integer>> ans = new ArrayList<>();
        if(root != null){
            // 全局记录节点
            List<Integer> path = new ArrayList<>();
            process(root, aim, 0, ans, path);
        }
        return ans;
    }

    // cur-当前节点，aim-目标值，sum-当前节点的上面节点的值的和
    public void process(TreeNode cur, int aim, int sum, List<List<Integer>> ans, List<Integer> path){
        if(cur.left == null && cur.right == null){
            // 到达叶节点，如果此时从根节点到叶子结点的这条路径的值的和等于目标值，则记录这条路径
            if(sum + cur.val == aim){
                // 将当前节点加入到全局路径中
                path.add(cur.val);
                // 将此时的全局路径，存放到全局结果中。
                copy(ans, path);
                // 恢复现场
                path.remove(path.size() - 1);
            }
        }else {
            // 不是叶节点，// 将当前节点加入到全局路径中
            path.add(cur.val);
            if(cur.left != null){
                process(cur.left, aim, sum + cur.val, ans, path);
            }
            if(cur.right != null){
                process(cur.right, aim, sum + cur.val, ans, path);
            }
            // 恢复现场
            path.remove(path.size() - 1);
        }
    }

    public void copy(List<List<Integer>> ans, List<Integer> path){
        List<Integer> tmp = new ArrayList<>();
        for (Integer num : path) {
            tmp.add(num);
        }
        ans.add(tmp);
    }
}
